package com.zxyankh.leetcode.question.chinese;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * <p>
 * 如果数组中不存在目标值，返回 [-1, -1]。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 * 示例 2:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: [-1,-1]
 *
 * @author zxyAnkh
 */
public class No34 {

    public static void main(String[] args) {
        No34 no34 = new No34();
        System.out.println(no34.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8));
        System.out.println(no34.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6));
        System.out.println(no34.searchRange(new int[]{2, 2}, 2));
        System.out.println(no34.searchRange(new int[]{1, 2, 3, 3, 3, 3, 4, 5, 9}, 3));
    }

    public int[] searchRange(int[] nums, int target) {
        // 各种特例
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        if (nums.length == 1) {
            if (nums[0] == target) {
                return new int[]{0, 0};
            } else {
                return new int[]{-1, -1};
            }
        }
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return new int[]{-1, -1};
        }
        if (target == nums[0]) {
            int i = 1;
            for (; i < nums.length; i++) {
                if (nums[i] != target) {
                    break;
                }
            }
            return new int[]{0, i - 1};
        }
        if (target == nums[nums.length - 1]) {
            int i = nums.length - 2;
            for (; i >= 0; i--) {
                if (nums[i] != target) {
                    break;
                }
            }
            return new int[]{i + 1, nums.length - 1};
        }

        // 二分查找
        int[] n = new int[]{-1, -1};

        return search(nums, target, 0, nums.length - 1, n);
    }

    private int[] search(int[] nums, int target, int left, int right, int[] n) {
        if (right - left <= 1) {
            return n;
        }
        int m = (left + right) / 2;
        if (nums[m] == target) {
            n[0] = m;
            n[1] = m;
            // 如果找到了，那就顺延往两边找
            for (int i = m; i >= left; i--) {
                if (nums[i] != target) {
                    n[0] = i + 1;
                    break;
                }
            }
            for (int i = m; i <= right; i++) {
                if (nums[i] != target) {
                    n[1] = i - 1;
                    break;
                }
            }
            return n;
        } else if (nums[m] < target) {
            return search(nums, target, m, right, n);
        } else {
            return search(nums, target, left, m, n);
        }
    }

}
